package Offer.offer2019;

/**
 * 斐波那契数列
 * @author: leiwenkang02@meituan.com
 * @date: 2019/4/22
 * @time: 19:47
 */
public class Offer09 {
    //方法一：递归
    public int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        }

        if (n <= 1) {
            return 1;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    //方法二：循环 动态规划
    public int fibonacci2(int n) {
        if (n <= 0) {
            return 0;
        }

        if (n <= 1) {
            return 1;
        }

        int fibOne = 0;
        int fibTwo = 1;

        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = fibOne + fibTwo;
            fibOne = fibTwo;
            fibTwo = result;
        }

        return result;
    }


}
